﻿#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

static int magic(unordered_set<int>& setA, unordered_set<int>& setB)
{
	int totalA = 0;
	int sizeA = setA.size();
	for (auto it = setA.begin(); it != setA.end(); it++)
	{
		totalA += *it;
	}

	float avgA = (float)totalA / sizeA;

	int totalB = 0;
	int sizeB = setB.size();
	for (auto it = setB.begin(); it != setB.end(); it++)
	{
		totalB += *it;
	}

	float avgB = (float)totalB / sizeB;
	if (avgA == avgB) return 0;

	unordered_set<int>* largerSet;
	unordered_set<int>* smallerSet;
	int largerTotal = 0;
	int smallerTotal = 0;
	int largerSize = 0;
	int smallerSize = 0;
	float largerAvg = 0.f;
	float smallerAvg = 0.f;

	if (avgA > avgB)
	{
		largerSet = &setA;
		smallerSet = &setB;
		largerTotal = totalA;
		smallerTotal = totalB;
		largerSize = sizeA;
		smallerSize = sizeB;
		largerAvg = avgA;
		smallerAvg = avgB;
	}
	else
	{
		largerSet = &setB;
		smallerSet = &setA;
		largerTotal = totalB;
		smallerTotal = totalA;
		largerSize = sizeB;
		smallerSize = sizeA;
		largerAvg = avgB;
		smallerAvg = avgA;
	}

	vector<int> numbersBetweenLargerAvgAndSmallerAvg;
	for (auto it = largerSet->begin(); it != largerSet->end(); it++)
	{
		int cur = *it;
		if (cur > smallerAvg && cur < largerAvg)
		{
			numbersBetweenLargerAvgAndSmallerAvg.push_back(cur);
		}
	}

	sort(numbersBetweenLargerAvgAndSmallerAvg.begin(), numbersBetweenLargerAvgAndSmallerAvg.end(), less<int>());

	int times = 0;
	while (numbersBetweenLargerAvgAndSmallerAvg.size() > 0 && largerSize > 1)
	{
		auto willMovedNum = numbersBetweenLargerAvgAndSmallerAvg.at(0);
		largerAvg = (float)(largerTotal - willMovedNum) / (largerSize - 1);
		bool isWillMovedNumInSmallerSet = smallerSet->find(willMovedNum) != smallerSet->end();
		if (!isWillMovedNumInSmallerSet)
		{
			smallerAvg = (float)(smallerTotal + willMovedNum) / (smallerSize + 1);
		}

		if (largerAvg > smallerAvg)
		{
			++times;
			largerTotal -= willMovedNum;
			--largerSize;
			largerSet->erase(willMovedNum);
			if (!isWillMovedNumInSmallerSet)
			{
				smallerTotal += willMovedNum;
				++smallerSize;
				smallerSet->insert(willMovedNum);
			}

			numbersBetweenLargerAvgAndSmallerAvg.clear();
			for (auto it = largerSet->begin(); it != largerSet->end(); it++)
			{
				int cur = *it;
				if (cur > smallerAvg && cur < largerAvg)
				{
					numbersBetweenLargerAvgAndSmallerAvg.push_back(cur);
				}
			}

			sort(numbersBetweenLargerAvgAndSmallerAvg.begin(), numbersBetweenLargerAvgAndSmallerAvg.end(), less<int>());
		}
		else
		{
			break;
		}
	}

	return times;
}

/**
 * 给一个包含n个整数元素的集合a，一个包含m个整数元素的集合b。
 * 定义magic操作为，从一个集合中取出一个元素，放到另一个集合中，且操作过后每个集合的平均值都大于操作前。
 * 注意以下两点：
 * 1. 不可以把一个集合的元素取空，这样就没有平均值了
 * 2. 值为x的元素从集合b取出放入集合a，但集合a中已经有值为x的元素，则a的平均值不变(因为集合元素不会重复)，
 * b的平均值可能会改变(因为x被取出了)
 *
 * 问最多可以进行多少次magic操作?
 *
 * 注意点：
 * 1. 两个集合的平均值如果相同，则无论怎么移动元素，都不可能达到两个集合的平均值都变大
 * 2. 平均值大的集合向平均值小的集合移动元素，要移动介于两个集合平均值之间的元素，而且，应该从这些元素选择尽可能小的来移动，
 * 这样才能保证移动的个数最多。
 *
 */
int main_SetA_MagicTo_SetB()
{
	int numbersA[] = {1,2,3,4};
	int countA = sizeof(numbersA) / sizeof(int);
	unordered_set<int> setA;
	int numbersB[] = {4,6,7,8};
	int countB = sizeof(numbersB) / sizeof(int);
	unordered_set<int> setB;
	
	for (int i = 0; i < countA; i++)
	{
		setA.insert(numbersA[i]);
	}

	for (int i = 0; i < countB; i++)
	{
		setB.insert(numbersB[i]);
	}

	int times = magic(setA, setB);
	printf("%d", times);

	return 0;
}